import java.util.*;

public class Leetcode210 {

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if (numCourses<=0){
            return new int[]{0};
        }
        int plen = prerequisites.length;
        if (plen == 0) {
            // 没有有向边，则表示不存在课程依赖，任务一定可以完成
            int[] ret = new int[numCourses];
            for (int i = 0; i < numCourses; i++) {
                ret[i] = i;
            }
            return ret;
        }
        Set<Integer>[] sets = new HashSet[numCourses];
        for (int i = 0; i < numCourses; i++) {
            sets[i] = new HashSet<>();
        }
        // 入度列表
        int[] inDergee = new int[numCourses];
        for (int[] p : prerequisites) {
            sets[p[1]].add(p[0]);
            inDergee[p[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < inDergee.length; i++) {
            if (inDergee[i]==0){
                queue.offer(i);
            }
        }
        int[] result = new int[numCourses];
        int index = 0;
        while (!queue.isEmpty()){
            Integer poll = queue.poll();
            result[index++] = poll;
            Set<Integer> set = sets[poll];
            for (Integer integer : set) {
                inDergee[integer]--;
                if (inDergee[integer]==0){
                    queue.offer(integer);
                }
            }
        }
        // 如果结果集中的数量不等于结点的数量，就不能完成课程任务，这一点是拓扑排序的结论
        if (index == numCourses) {
            return result;
        }
        return new int[0];
    }
}
